package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         31,
		Discription: "下一个字典序排列",
		Level:       2,
		Labels: map[string]int{
			"双指针滑动": 1,
		},
	})
}

// 思路：
// 从后向前找第一个i，使得nums[i]<nums[i+1]，这个时候nums[i+1:]是非递增的
// 再从后向前找第一个j，使得nums[j]>nums[i]
// 交换i j的值，这个时候nums[i+1:]依然是非递增的
// 此时我们已经在尽可能小的位置换了一个增幅尽可能小的值，再把之后的非递减子数组翻转，就是下一个字典序
func NextPermutation(nums []int) {
	if len(nums) <= 1 {
		return
	}

	reverse := func(left, right int) {
		for left < right {
			nums[left], nums[right] = nums[right], nums[left]
			left++
			right--
		}
	}

	n := len(nums)
	i := n - 2
	for ; i >= 0; i-- {
		if nums[i] < nums[i+1] {
			break
		}
	}

	if i < 0 {
		reverse(0, n-1)
		return
	}

	j := n - 1
	for ; j > i; j-- {
		if nums[j] > nums[i] {
			break
		}
	}

	nums[i], nums[j] = nums[j], nums[i]
	left := i + 1
	right := n - 1
	reverse(left, right)
}
